package com.hyc.DataStructure.tree;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: BinaryTreeDemo
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/3 16:47
 * @version: 1.0
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        //  测试，先创建一颗二叉树
        BinaryTree binaryTree = new BinaryTree();
        heroNode root = new heroNode(1, "宋江");
        heroNode node1 = new heroNode(2, "吴用");
        heroNode node2 = new heroNode(3, "卢俊义");
        heroNode node3 = new heroNode(4, "林冲");
        heroNode node4 = new heroNode(5, "关胜");
        //设置头节点
        binaryTree.setHead(root);
        // 此处我们手动的填补二叉树，之后还会有递归的方式填充二叉树
        root.setLeftNode(node1);
        root.setRightNode(node2);
        node2.setRightNode(node3);
        node2.setLeftNode(node4);
        //测试
        ////    前序遍历
        //binaryTree.PreOrder();
        ////中序遍历
        //System.out.println();
        //binaryTree.InfixOrder();
        ////后序遍历
        //System.out.println();
        //binaryTree.PostOrder();


        //System.out.println("前中后查找");
        //System.out.println("开始前序查找");
        //heroNode resNode = binaryTree.preOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始中序查找");
        //heroNode resNode = binaryTree.infixOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}
        //System.out.println("开始后序查找");
        //heroNode resNode = binaryTree.postOrderSearch(5);
        //if (resNode != null) {
        //    System.out.printf("找到节点为 no =>%d,名字 name => %s ", resNode.getId(), resNode.getName());
        //} else {
        //    System.out.println("查找失败");
        //}

        //    删除测试
        System.out.println("删除前");
        binaryTree.PreOrder();
        System.out.println("删除后");
        binaryTree.deleteNode(5);
        binaryTree.PreOrder();

    }
}


class BinaryTree {
    //确定根节点
    private heroNode head;

    public void setHead(heroNode head) {
        this.head = head;
    }

    //   前序遍历
    public void PreOrder() {
        if (this.head != null) {
            this.head.PreOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }

    //中序遍历
    public void InfixOrder() {
        if (this.head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }

    //后续遍历
    public void PostOrder() {
        if (this.head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树没有根节点，无法遍历");
        }
    }

    //前序查找
    public heroNode preOrderSearch(int no) {
        if (this.head != null) {
            return this.head.PreOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序查找
    public heroNode infixOrderSearch(int no) {
        if (this.head != null) {
            return this.head.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //后序查找
    public heroNode postOrderSearch(int no) {
        if (this.head != null) {
            return this.head.postOrderSearch(no);
        } else {
            return null;
        }
    }


    //    删除节点
    public void deleteNode(int no) {
        if (head != null) {
            if (head.getId() == no) {
                head = null;
                return;
            } else {
                head.deleteNode(no);
            }
        } else {
            System.out.println("空树,无法删除");
        }
    }
}

class heroNode {
    private int id;
    private String name;
    private heroNode leftNode;
    private heroNode rightNode;

    public heroNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(heroNode leftNode) {
        this.leftNode = leftNode;
    }

    public heroNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(heroNode rightNode) {
        this.rightNode = rightNode;
    }

    public heroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return "heroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    public void setName(String name) {
        this.name = name;

    }

    //    前序遍历
    public void PreOrder() {
        System.out.println(this);
        if (this.getLeftNode() != null) {
            this.leftNode.PreOrder();
        }
        if (this.getRightNode() != null) {
            this.rightNode.PreOrder();
        }
    }

    //    中序遍历
    public void infixOrder() {
        if (this.leftNode != null) {
            this.leftNode.infixOrder();
        }
        System.out.println(this);
        if (this.rightNode != null) {
            this.rightNode.infixOrder();
        }
    }

    //   后序遍历
    public void postOrder() {
        if (this.leftNode != null) {
            this.leftNode.postOrder();
        }
        if (this.rightNode != null) {
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }

    //   前序查找
    public heroNode PreOrderSearch(int no) {
        System.out.println("前序查找");
        //比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.PreOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归前序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.PreOrderSearch(no);
        }
        return resNode;
    }

    //   中序查找
    public heroNode infixOrderSearch(int no) {

        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.infixOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //比较当前节点的no 是不是我们要搜索的
        System.out.println("中序查找");
        if (this.id == no) {
            return this;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归中序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }

    //   后序查找
    public heroNode postOrderSearch(int no) {

        //要返回的节点
        heroNode resNode = null;
        //  判断左边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.leftNode != null) {
            resNode = this.leftNode.postOrderSearch(no);
        }
        //如果不为null 那么代表左边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        //  判断右边节点是不是空 如果不是空的话 那么就递归后序查找
        //    如果找到的话 就返回找到的节点
        if (this.rightNode != null) {
            resNode = this.rightNode.postOrderSearch(no);
        }
        //如果不为null 那么代表右边找到了直接返回即可
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序查找");
        //左右子树，都没有找到，那么就比较当前节点的no 是不是我们要搜索的
        if (this.id == no) {
            return this;
        }
        return resNode;
    }


    //    删除 
    public void deleteNode(int no) {
        //    向左边遍历 如果左边子树有点话就将左边子树置空，如果不是就遍历右边
        if (this.leftNode != null && this.leftNode.id == no) {
            this.leftNode = null;
            return;
        }
        //    向右边遍历 如果右边子树有点话就将左边子树置空，如果左右都没有那么就绪要递归的删除
        if (this.rightNode != null && this.rightNode.id == no) {
            this.rightNode = null;
            return;
        }
        //    如果上面两步都不成功那么我们先向左边递归删除
        if (this.leftNode != null) {
            this.leftNode.deleteNode(no);
        }

        //    如果递归删除左子树也没有成功删除，那么就递归删除右边子树
        if (this.rightNode != null) {
            this.rightNode.deleteNode(no);
        }
    }

}